package com.ycy.leetcode.offer;

import org.junit.Test;

public class Offer13 {

  int res = 0;

  public static void main(String[] args) {
    Offer13 offer13 = new Offer13();
    int i = offer13.movingCount(11, 8, 16);
    System.out.println(i);
  }

  public int movingCount(int m, int n, int k) {
    //初始化
    boolean [][] board = new boolean[m][n];
    // for(int i=0;i<board.length;i++){
    //     for(int j =0 ;j<board[i].length;j++){
    //         dfs(0,0,board,k);
    //     }
    // }
    dfs(0,0,board,k);
    return res;
  }

  @Test
  public void test(){
    int sum = getSum(10);
    System.out.println(sum);
  }

  public int getSum(int i){
    int src = i;
    int sum = 0;
    do{
      int mo = i%10;
      i = i/10;
      sum = sum + mo;

    }while(i > 0);
//    System.out.print( "" + src + " = " + sum + ";");
    return sum;
  }

  public void dfs(int i,int j,boolean [][] board, int k){
    //越界终止
    if( i>=board.length ||
            i<0 ||
            j>=board[i].length ||
            j<0){
      return;
    }

    //大于k之和，终止
    if(k < (getSum(i) + getSum(j)) ){
      return;
    }
    //重复遍历终止
    if(board[i][j]){
      return;
    }
     System.out.print(i+","+j + ";");
    res++;

    board[i][j] = true;

    dfs(i,j-1,board,k);
    dfs(i-1,j,board,k);
    dfs(i,j+1,board,k);
    dfs(i+1,j,board,k);

    //这地方当心，重复遍历的就不用在遍历了，防止重复累加步数
    // board[i][j] = false;
    return;
  }

}
